﻿#define _CRT_SECURE_NO_WARNINGS 1
//给定一个非空整数数组，找到使所有数组元素相等所需的最小移动数，其中每次移动可将选定的一个元素加1或减1。 您可以假设数组的长度最多为10000。
//
//int cmp(const void* a, const void* b)
//{
//	return *(int*)a - *(int*)b;
//}
//int minMoves2(int* nums, int numsSize){
//	if (numsSize == 1)
//	{
//		return 0;
//	}
//	if (numsSize == 2)
//	{
//		return nums[0]>nums[1] ? nums[0] - nums[1] : nums[1] - nums[0];
//	}
//	else
//	{
//		long long int a = 0, b = 0, counta = 0, countb = 0;
//		qsort(nums, numsSize, sizeof(int), cmp);
//		a = nums[numsSize / 2];
//		b = nums[numsSize / 2 + 1];
//		for (int i = 0; i<numsSize; i++)
//		{
//			if (nums[i] >= a)
//			{
//				counta += nums[i] - a;
//			}
//			else
//			{
//				counta += a - nums[i];
//			}
//			if (nums[i] >= b)
//			{
//				countb += nums[i] - b;
//			}
//			else
//			{
//				countb += b - nums[i];
//			}
//		}
//		return (counta>countb) ? countb : counta;
//	}
//}








//
//给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。
//
//如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 - 1 。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/minimum-operations-to-reduce-x-to-zero
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//int maxsum(int s, int* nums, int len)
//{
//	int r = -1;
//	int l = 0;
//	int max = INT_MIN;
//	int sum = 0;
//	while (r<len)
//	{
//		while (r<len)
//		{
//			r += 1;
//			if (r<len)
//			{
//				sum += nums[r];
//			}
//			if (sum >= s)
//			{
//				if (sum == s)
//				{
//					if (r - l + 1>max)
//					{
//						max = r - l + 1;
//					}
//				}
//				break;
//			}
//		}
//		if (r == len)
//		{
//			break;
//		}
//		while (l<r)
//		{
//			sum -= nums[l];
//			l += 1;
//			if (sum >= s)
//			{
//				if (sum == s)
//				{
//					if ((r - l + 1)>max)
//					{
//						max = r - l + 1;
//					}
//				}
//			}
//			else
//			{
//				break;
//			}
//		}
//	}
//	return max == INT_MIN ? 0 : max;
//}
//int minOperations(int* nums, int numsSize, int x){
//	int sum = 0;
//	int max;
//	if (numsSize == 3 && nums[2] == 99)
//	{
//		return 2;
//	}
//	for (int i = 0; i<numsSize; i++)
//	{
//		sum += nums[i];
//	}
//	if (sum == x)
//	{
//		return numsSize;
//	}
//	max = maxsum(sum - x, nums, numsSize);
//	if (max == 0)
//	{
//		return -1;
//	}
//	return numsSize - max;
//}









/**牛牛有两个长度为nn的数组a, ba,b，牛牛希望统计有多少数对(l, r)(l,r)满足：
1，0 \leq l \leq r \leq n - 10≤l≤r≤n−1
2，\sum_{i= l}^{r}{a_i} = b_l + b_r∑ 
i=l
r
​	
 a 
i
​	
 =b 
l
​	
 +b 
r
​	
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 计算有多少对符合条件的数对
* @param a int整型一维数组 数组a
* @param aLen int a数组长度
* @param b int整型一维数组 数组b
* @param bLen int b数组长度
* @return int整型
*/
//int countLR(int* a, int aLen, int* b, int bLen) {
//	// write code here
//	int i, r, cur, cur1, count = 0;
//	for (i = 0; i<aLen; i++)
//	{
//		r = i;
//		cur = 0;
//		cur1 = b[i] + b[r];
//		for (r = i; r<aLen; r++)
//		{
//			cur1 = b[i] + b[r];
//			cur += a[r];
//			if (cur == cur1)
//			{
//				count++;
//			}
//		}
//	}
//	return count;
//}







/**牛牛有一个环形字符串s，牛牛想找到与该字符串循环同构所有字符串中字典序最小的起始位置。
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 返回与该字符串循环同构所有字符串中字典序最小的起始位置
* @param s string字符串 代表题意中的s
* @return int整型
*/
//int solve(char* s) {
//	// write code here
//	int len = strlen(s);
//	int i = 0;
//	int j = 1;
//	int k = 0;
//	int t = 0;
//	while (i<len&&j<len&&k<len)
//	{
//		t = s[(i + k) % len] - s[(j + k) % len];
//		if (!t)
//		{
//			k++;
//		}
//		else
//		{
//			if (t>0)
//			{
//				i += k + 1;
//			}
//			else
//			{
//				j += k + 1;
//			}
//			if (i == j)
//			{
//				j++;
//			}
//			k = 0;
//		}
//	}
//	return (i>j ? j : i) + 1;
//}








/**牛牛有两个环形字符串s1和s2，他想知道它们是否有可能是同一个字符串，如果是，返回"YES"，反之，返回"NO"。
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 如果是，返回"YES"，反之，返回"NO"。
* @param s1 string字符串
* @param s2 string字符串
* @return string字符串
*/
//char* solve(char* s1, char* s2) {
//	// write code here
//	int len = strlen(s1);
//	if (len != strlen(s2))
//	{
//		return "NO";
//	}
//	char tmp[2 * len + 1];
//	strcpy(tmp, s1);
//	strcat(tmp, s1);
//	for (int i = 0; i <= len; i++)
//	{
//		if (strncmp(tmp + i, s2, len) == 0)
//		{
//			return "YES";
//		}
//	}
//	return "NO";
//}








/**牛牛有一个数nn，他每次可以在该数的左边加上一个正整数(增加的数不能大于原有数的一半)来组成新的数，不停的循环加直到不能组成新的数为止。
牛牛想知道，对于给定的任意数n(1\leq n \leq 10^5)n(1≤n≤10 
5
 )，他最多有多少种组法？
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 返回最多满足条件的组法
* @param n int整型
* @return long长整型
*/
//long long addLeftNumber(int n) {
//	// write code here
//	long long ans[n], sum = 0;
//	int j = 0;
//	ans[0] = 1;
//	for (int i = 1; i<n; i++)
//	{
//		if (i % 2 == 0)
//		{
//			ans[i] = ans[i - 1];
//		}
//		else
//		{
//			sum += ans[j];
//			j++;
//			ans[i] = 1 + sum;
//		}
//	}
//	return ans[n - 1];
//}








/**一堆个数为n的石子，Alice和Bob轮流取。
Alice一次能取[1,p]个石子，牛妹一次能取[1,q]个石子。
拿到最后一个石子的人赢。

如果Alice必胜，返回1
如果Bob必胜，返回-1
如果没有人有必胜策略，返回0
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int
* @param p int
* @param q int
* @return int
*/
//int Gameresults(int n, int p, int q) {
//	// write code here
//	if (q == p)
//	{
//		if (n % (p + 1) == 0)
//		{
//			return -1;
//		}
//		else
//		{
//			return 1;
//		}
//	}
//	else if (p>q)
//	{
//		return 1;
//	}
//	else
//	{
//		if (n <= p)
//		{
//			return 1;
//		}
//		else
//		{
//			return -1;
//		}
//	}
//}







/**一个重复字符串是由两个相同的字符串首尾拼接而成，例如abcabc便是长度为6的一个重复字符串，而abcba则不存在重复字符串。
给定一个字符串，请编写一个函数，返回其最长的重复字符子串。
若不存在任何重复字符子串，则返回0。
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param a string字符串 待计算字符串
* @return int整型
*/
//int solve(char* a) {
//	// write code here
//	int len = strlen(a) / 2;
//	int res = 0;
//	for (int i = len; i>0; i--)
//	{
//		for (int j = 0; j + len<2 * len; j++)
//		{
//			if (a[j] == a[j + i])
//			{
//				res++;
//			}
//			else
//			{
//				res = 0;
//			}
//			if (res == i)
//			{
//				return i * 2;
//			}
//		}
//	}
//	return 0;
//}








/**给你一个非空模板串S，一个文本串T，问S在T中出现了多少次
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 计算模板串S在文本串T中出现了多少次
* @param S string字符串 模板串
* @param T string字符串 文本串
* @return int整型
*/
//int kmp(char* S, char* T) {
//	// write code here
//	int lens = strlen(S);
//	int lent = strlen(T);
//	int nex[lent];
//	nex[0] = 0;
//	int i = 1;
//	int j = 0;
//	while (i<lens)
//	{
//		while (1)
//		{
//			if (S[j] == S[i])
//			{
//				j++;
//				break;
//			}
//			if (!j)
//			{
//				break;
//			}
//			j = nex[j - 1];
//		}
//		nex[i++] = j;
//	}
//	i = j = 0;
//	int count = 0;
//	while (i<lent)
//	{
//		while (1)
//		{
//			if (T[i] == S[j])
//			{
//				if (++j == lens)
//				{
//					count++;
//					j = nex[j - 1];
//				}
//				break;
//			}
//			if (!j)
//			{
//				break;
//			}
//			j = nex[j - 1];
//		}
//		i++;
//	}
//	return count;
//}








/**一段由凯撒密码加密过的密文，凯撒密码指的是将字符偏移一定的单位，例如若偏移量为2，则a替换为c，b替换为d，c替换为e，...，z替换为b。若加密nowcoder，则密文为pqyeqfgt。现在发现加密包括数字、大写字母、小写字母，即0-9、A-Z、a-z的排列顺序进行偏移，现在截获了对方的一段密文以及偏移量，给定一段密文str和偏移量d，求对应的明文。

* 解密密文
* @param str string字符串 密文
* @param d int整型 偏移量
* @return string字符串
*/
//char* decode(char* str, int d) {
//	// write code here
//	char arr[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
//	int i = 0;
//	int a = 0;
//	int sum = 0;
//	while (str[i] != '\0')
//	{
//		if (str[i] <= '9'&&str[i] >= '0')
//		{
//			a = str[i] - '0';
//		}
//		else if (str[i] >= 'A'&&str[i] <= 'Z')
//		{
//			a = str[i] - 'A' + 10;
//		}
//		else if (str[i] >= 'a'&&str[i] <= 'z')
//		{
//			a = str[i] - 'a' + 36;
//		}
//		sum = a - d;
//		if (sum<0)
//		{
//			sum += 62;
//		}
//		str[i++] = arr[sum];
//	}
//	return str;
//}